﻿#pragma once
#include "Index.h"

/**
 * 构建乘积数组.
 * https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/
 * 数组 前缀和
 * 
 * 给定一个数组 A[0,1,...,n-1] ,请构建一个数组 B[0,1,...,n-1],
 * 其中 B 的元素 B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]（除 A[i] 以外的全部元素的的乘积）。
 * 程序中不能使用除法.
 */
namespace MakeMultiArray
{
	class Question
	{
	public:
		virtual std::vector<int> multiply(const std::vector<int>& A) = 0;
	};

	class Solution:Question
	{
	public:
		/**
		 * 将之前保留预计算值的栈 和 返回结果的数组合并,同样进行两次遍历，但优化空间复杂度O(n)->O(1)
		 * 时间复杂度:O(n) 空间复杂度(1)
		 */
		std::vector<int> multiply(const std::vector<int>& A) override
		{
			const int size = A.size();
			if (size < 1)
				return {};

			std::vector<int> result(size, 1);

			//从左到右遍历
			for (int i = 1; i < size; ++i)
				result[i] = result[i - 1] * A[i - 1];
			//从右到左遍历
			int multiAccum = 1;
			for (int i = size - 2; i >= 0; --i)
			{
				multiAccum *= A[i + 1];
				result[i] *= multiAccum;
			}

			return result;
		}
	};

	class Practice:public Question
	{
	public:
		std::vector<int> multiply(const std::vector<int>& A) override
		{
			if(A.size()<=1)
				return {};

			const int size=A.size();
			std::vector<int> result(size,1);

			//正向遍历
			int multi_cur=A.front();
			for(int i=1;i<size;++i)
			{
				result[i]*=multi_cur;
				multi_cur*=A[i];
			}

			//反向遍历
			multi_cur=A.back();
			for(int i=size-2;i>=0;--i)
			{
				result[i]*=multi_cur;
				multi_cur*=A[i];
			}

			return result;
		}
	};
}